At a fundamental level, all computer systems, including the initial primitive vacuum-tube-based computer systems developed in the 1940's, are data-storage machines which execute symbol-transformation operations on stored data. Initially, data was stored in small, volatile electronic memories within computer systems and on punched cards input to computer systems. As the capabilities of computer systems, and uses to which computer systems were put, rapidly expanded, a wide array of different types of volatile and non-volatile data-storage components were developed for computer systems, as well as computational subsystems and logical entities to facilitate creation, storage, retrieval, alteration, input, and output of data. Ultimately, separate database-management systems were developed to provide even higher-level database-management functionality.
Currently, very complex and highly capable database-management systems of a variety of different types are commercially available for managing data on a broad range of computer systems from personal computers all the way up to highly complex, distributed computer systems in which data is stored and managed over large numbers of computer systems and mass-storage systems interconnected by a variety of different communications media. Relational-database-management systems, based on a relational algebra that provides relatively simple and logical constructs and algebraic operations on those constructs, were initially developed in the late 1960's and 1970's, and continue to provide useful, flexible, and powerful database management in today's sophisticated, highly-distributed computing environments. Database administrators and users employ schema-development and schema-management commands to create an organizational framework for data and access data through query-language commands. The types of queries that may be executed may range from simple record retrieval to very complex queries requiring access and analysis of the contents of numerous different entities stored within a database, as well as creation of temporary, intermediate entities. There are often many different equivalent ways to express a given query, and there are generally a very great many different ways to decompose a query expressed in a high-level query language into fundamental database operations that are carried out by the database-management system to execute the query. The speed at which a particular query can be executed may vary greatly depending on which low-level database operations are chosen for to implement execution of a query and on the execution sequence of the low-level database operations. Query optimization is a field concerned with optimizing translation of high-level query-language queries into an efficient execution of a set of low-level operations. Despite enormous efforts in query-optimization research and development, there are still cases in which the query-execution plans produced by query optimizers may inadvertently lead to extremely time-inefficient query execution. Researchers and developers of database-management systems, vendors of database-management systems, manufacturers and vendors of computer hardware, and, ultimately, users of database-management systems and applications that interface to database-management systems continue to seek better query optimization techniques in order to optimize query-execution times and to meet other specified constraints that arise in the computational environments in which database-management systems operate.